---
title: "L2-022 重排链表"
created: 2025-11-28
tags:
  - 算法
---

# L2-022 重排链表

## 题目 [L2-022 重排链表](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805057860517888&page=1)

![[image-129349ef.png]]

## 思路分析

哈希模拟链表 保存原序和处理后顺序

## 代码实现

```cpp
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using Pll = pair<ll, ll>;
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
const int inf = 0x3f3f3f3f;

unordered_map<int, PII> node;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int head, n;
    cin >> head >> n;

    while (n--) {
        int addr, val, nxt;
        cin >> addr >> val >> nxt;
        node[addr] = {val, nxt};
    }

    vector<int> order;
    for (int i = head; i != -1; i = node[i].second) {
        order.push_back(i);
    }

    vector<int> result;
    int l = 0, r = order.size() - 1;
    while (l <= r) {
        if (r != l) result.push_back(order[r--]);
        result.push_back(order[l++]);
    }

    for (int i = 0; i < result.size(); ++i) {
        int addr = result[i];
        int nxt = (i + 1 < result.size()) ? result[i + 1] : -1;
        printf("%05d %d ", addr, node[addr].first);
        if (nxt == -1) printf("-1\n");
        else printf("%05d\n", nxt);
    }

    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-021 点赞狂魔|L2-021 点赞狂魔]] 🏠 [[00-天梯赛]] ➡️ [[L2-023 图着色问题|L2-023 图着色问题]]